// 先序遍历

function beforeMap(head){
    const res = [],stack =[head];

    while(stack.length){
        const node = stack.pop()
        res.push(node.var)
        node.right && stack.push(node.right)
        node.left && stack.push(node.left)
    }

    return res
}

// 后序遍历

function afterMap(head){
    const res = [], stack = [head];
    while(stack.length){
        const node = stack.pop()
        res.push(node.var)
        node.left && stack.push(node.left)
        node.right && stack.push(node.right)
    }
    return res
}

// 中序遍历
function middle(head){
    const res = [], stack = [], cur = head;
    while(stack || cur){
        if(cur){
           stack.push(cur)
           cur = cur.left
        }else{
            cur = stack.pop()
            res.push(cur.var)
            cur = cur.right
        }
    }
}




// 递归遍历

function commonWay(head){
    const res = []
    
    function tools(node){
        if(node){
            res.push(node.var)
            node.left && tools(node.left)
            node.right && tools(node.right)
        }
    }
    tools(head)
    return res
}


// 统一迭代法

// 先序
function tongyiMap(head){
    const res = [], stack = [head];
    while(stack.length){
        const node = stack.pop()
        if(!node){
            res.push(stack.pop().var)
            continue;
        }

        node.right && stack.push(node.right) // 右
        node.left && stack.push(node.left) // 左
        stack.push(node) //中
        stack.push(null)
    }
}


